package arithmetic;

import java.util.Arrays;

/**
 * 下面两个算法非常重要： 归并排序和二分查找
 * <p>
 * 归并排序（时间复杂度：线性对数级NlogN）:
 * 二分查找（对数级别）
 */
public class MergeSortAndBesection {


    public static void main(String[] args) {
        int arr[] = {-1, 2, 3, 4, -5, 0, -4, 2, 4, 2, 5, 1, 5, -23, -9, 5, 2, -8, 10, 7, -15, 6, 13, 6, -9, -8, -78, -70, 70, 4, 4, 5, -5};
        int besection = MergeSortAndBesection.besection(arr, -78);
        System.out.println(besection);
    }


    /**
     * 二分查找思想：  在一个集合中寻找某个值，先将数据排序，然后target和中间结果arr[n/2]比较，如果：target<arr[n/2]     说明结果在arr[0]~arr[n/2]之间
     * 下次查找该值就在arr[0]~arr[n/2]中间查找。
     */

    public static int besection(int arr[], int target) {
        Arrays.sort(arr);
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int middle = (right + left) / 2;
            if (target - arr[middle] > 0) {
                left = middle + 1;
            }
            if (target - arr[middle] < 0) {
                right = middle - 1;
            }
            if (target - arr[middle] == 0) {
                return middle;
            }
        }
        return 0;
    }

}
